package com.breeze.leetcode.middle;

import java.util.Arrays;

/**
 * @url <a href="https://leetcode.cn/problems/magnetic-force-between-two-balls">1552. 两球之间的磁力</a>
 * @author yangzh
 * @date 2025/2/14
 */
public class T1552MagneticForceBetweenTwoBalls {
    public static void main(String[] args) {
        T1552MagneticForceBetweenTwoBalls solution = new T1552MagneticForceBetweenTwoBalls();
        int[] position = {1,2,3,4,7};
        int result = solution.maxDistance(position, 3);
        System.out.println(result);
    }

    /**
     * 求固定几个点之间的最大距离
     * 1 2 3 4 7
     * 1 2 3 4 5 100
     * 3 4 5 7 9
     * 99 1
     */
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1] - position[0], res = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int current = position[0], balls = 1;
            for (int i = 1; i < position.length; i++) {
                if (position[i] - current >= mid) {
                    current = position[i];
                    balls++;
                }
            }

            if (balls >= m) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }
}
